Abstract: This talk presents a universality result for correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously $O(1)$-approximate for all $\ell_p$-norms $(1 \leq p \leq \infty)$ of the disagreement vector; in other words, a combinatorial $O(1)$-approximation of the all-norms objective for correlation clustering. This is the first proof that minimal sacrifice is needed in order to optimize different norms of the disagreement vector, where each norm captures some balance between average welfare $(p=1)$ and fairness $(p=\infty)$. Prior to this work, it was not known whether an all-norms solution existed for correlation clustering, and to the best of our knowledge, this is the first all-norms result for a clustering problem more generally.
In addition, our algorithm is the first combinatorial approximation algorithm for the $\ell_2$-norm objective, and more generally the first combinatorial algorithm for the $\ell_p$-norm objective when $1 < p < \infty$. It is also faster than all previous algorithms that minimize the $\ell_p$-norm of the disagreement vector, with run-time $O(n^\omega)$, where $O(n^\omega)$ is the time for matrix multiplication on $n$ by $n$ matrices.
This is based on joint work with Sami Davies and Benjamin Moseley; https://arxiv.org/abs/2308.01534.